/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.algorithm.search;

import java.util.PriorityQueue;

import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;
import kaist.sep502.tsp.model.Solution;

/**
 * @author minho kim
 *
 */
public class UniformCostSearch extends SearchAlgorithm {
	/**
	 * @param problem
	 */
	public UniformCostSearch(Problem problem) {
		super(problem);
	}

	private PriorityQueue<CityPath> frontier;
	
	public Solution search(){
		solution = new Solution("Uniform Cost");
		solution.expandedNodeCount = 0;
		solution.startStopWatch();
		
		// 1. 초기화 : Frontier 생성/초기화, Explored 생성/초기화, 알고리즘 선
		frontier = new PriorityQueue<CityPath>(2000000); 
		CityPath cityPath = new CityPath(problem, problem.departureCityNo);
		frontier.add(cityPath);
		
		PriorityQueue<CityPath> goalCityPaths = new PriorityQueue<CityPath>();
		
		// 2. 검색 처리 : goal 체크,
		while(frontier.isEmpty() != true){
			solution.expandedNodeCount++;
			
			// 2.2 하나의 탐색 대상 도시를 꺼냄 
			cityPath = frontier.poll();
			
			// 2.3 Goal인지 체크하고 맞다면 솔루션을 리턴한다.
			if(problem.checkGoal(cityPath)){
				goalCityPaths.add(cityPath);
				continue;
			}
			
			// 2.4 주변 도시를 찾아서 검색 대상 목록(Frontier)에 추가한다.
			handleFrontier(cityPath);
		}
		
		if(goalCityPaths.isEmpty() != true){
			cityPath = goalCityPaths.poll();
			solution.setGoalCityPath(cityPath);
			solution.setSuccess(true);
			solution.stopStopWatch();
		}
		
		return solution;
	}

	public void handleFrontier(CityPath cityPath) {
		int citySize = problem.citySize;
		
		try{
			// 마지막 도시까지 다 여행했는지 여부에 따라 처리가 달라짐 
			int tourHistorySize = cityPath.tourHistory.size(); 
			if(tourHistorySize == citySize){
				cityPath.moveTo(problem, problem.departureCityNo, 0.0);
				frontier.add(cityPath);
				return;
			}
			
			// 마지막 도시까지 여행을 하지 않은 경우 이웃도시를 찾아서 리턴한다.
			// i는 cityNo가 아님.
			int tempCityNo;
			for(int i=0; i < citySize; i++){
				tempCityNo = problem.cityList.get(i).getCityNo();
				// 이미 들렸던 도시이면 Skip
				if(cityPath.tourHistory.contains(tempCityNo)){
					continue;
				}
				
				CityPath newCityPath = cityPath.clone();
				newCityPath.moveTo(problem, tempCityNo, 0.0);
				
				if(frontier.contains(newCityPath)){
					continue;
				}
				
				frontier.add(newCityPath);
			}
			
		} catch (Exception e){
			e.printStackTrace();
		}
		
	}
}
